package me.eg.third;

import me.eg.util.TreeNode;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 * <p>
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 * <p>
 * 注意:
 * 你可以假设树中没有重复的元素。
 * <p>
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 */
public class BuildTree {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, postorder, 0, inorder.length - 1, postorder.length - 1);
    }

    private TreeNode buildTree(int[] inorder, int[] postOrder, int inStart, int inEnd, int postIndex) {
        if (inStart > inEnd) return null;

        int i;
        for (i = inStart; i <= inEnd; i++) {
            if (inorder[i] == postOrder[postIndex]) break;
        }
        TreeNode root = new TreeNode(postOrder[postIndex]);
        root.left = buildTree(inorder, postOrder, inStart, i - 1, postIndex - (inEnd - i) - 1);
        root.right = buildTree(inorder, postOrder, i + 1, inEnd, postIndex - 1);
        return root;
    }
}
